typedef int ElemType;
typedef struct SqNode{
	ElemType key;
	InfoType other;
}SqNode, SqList[m+1];
typedef struct Heap{
	SqList data;
	int length;
}HeapType;
void HeapAdjust(HeapType &H, int bottom, int top){
	SqNode tmp = H.data[bottom];
	for (int i = 2 * bottom; i <= top; ++i){
		if (i < top && H.data[i].key > H.data[i+1].key){
			++i;
		}
		if (tmp.key > H.data[i].key){
			H.data[bottom] = H.data[i]; bottom = i;
		}
		else {
			H.data[bottom] = tmp; break;
		}
	}
}
void HeapSort(HeapType &H){
	int len = H.length;
	SqNode tmp;
	for (int i = len / 2; i > 0; --i){
		HeapAdjust(H, i, len);
	}
	for (int i = len; i > 0; --i){
		tmp = H.data[i];
		H.data[i] = H.data[1]; H.data[1] = tmp;
		HeapAdjust(H, 1, i - 1);
	}
}

//again
#define m 1000
typedef int ElemType;
typedef struct SqNode{
	ElemType key;
	InfoType other;
}SqNode, SqList[m+1];
typedef struct HeapType{
	SqList data;
	int length;
}HeapType;
void HeapAdjust(HeapType &H, int bottom, int top){
	H.data[0] = H.data[bottom];
	for (int i = 2 * bottom; i <= top; i *= 2){
		if (i < top && H.data[i].key > H.data[i+1].key){
			++i;
		}
		if (H.data[0].key > H.data[i].key){
			H.data[i] = H.data[0]; bottom = i;
		}
		else break;
	}
	H.data[bottom] = H.data[0];
}
void HeapSort(HeapType &H){
	int len = H.length;
	for (int i = len / 2; i > 0; --i){
		HeapAdjust(H, i, len);
	}
	for (int i = len; i > 1; --i){
		H.data[0] = H.data[i];
		H.data[i] = H.data[1]; H.data[1] = H.data[0];
		HeapAdjust(H, 1, i - 1);
	}
}